Make a LispをPureScriptでやった
つまり、malというLisp方言をPureScriptで実装した ↑に書いているが、Lispの処理系を書く題材みたいなもの
CやPythonなど、メジャーな言語はだいたい既に実装されているし、
makeやJSONやjqなど、「それで言語処理系書けるん！？」という感じの実装もある
ない言語も存在する(例えば2021/12/18現在V言語の実装はない)
成り行き
元々は「継続」の概念を理解したくて、Gaucheの本を眺めたりしていた
しかし、Lispをまともにやったことがないので地味に詰まる
とは言え、Lisp自体を学ぶモチベーションがそこまでなかった
実装例を眺めているとちょうどPureScriptがなかったので、PureScriptでやってみるか、となった
当時PureScriptは触り始めで、これで何かを書いたことがなかったのでちょうどよかった
Lispを学びながらPureScriptを学べるので一石二鳥mrsekut.icon
Haskellの知識がかなり活かせるので、PureScriptの学習はそこまで大変ではなかった
一応最後まで終わらしてPR出して、mergeしてもらった ref https://gyazo.com/82e2d748cbfae41733387de9ec5384f7
やっていき
あるいは、実装例を参考にしながら進めていく
あるいは、テストケースを参考にしながら進めていく
解説は11個のステップをやっていく
インクリメンタルに作っていく感じではない
最初にparserを作り終えて、次にevalを作って、そこから機能を足していく感じ
解説はあるが、内容はそこまで親切ではない
誰をターゲットにしているのかよくわからない
Lisp知っている人？言語処理系作ったことある人？
実装言語(ホスト言語)を規定していないので、解説しづらいので仕方ないところもある
言語処理系のノリを軽く知っていたのと、既存実装で読めるものがあったおかげでなんとかなった感じがする
主にHaskellとTypeScriptの実装を参考にした
最初はElmも見てたが無理やりな感じがあったので途中から見なくなった
関数型寄りの実装を見たいときはF#やElixirとかも見た
「defferable」という項目は、「実装を保留してもいいよ」というやつだが、そうするとtestがクリアしなくなって気持ち悪いので全部やりながら進めた
単体のtest caseがシンプルなのは理解の助けになった
途中まではReaderTパターンとかを使って独自に進めていたが、段々詰まってきたので、途中でbranchを変えて、Haskellの実装をなぞるようにして実装を進めた
つまり、既にセルフホストされた実装が存在する
そのため、「自分で作ったmalで、malを書き直す」という作業をスルーできる
「自分で作ったmalを、そのmal実装上で動かす」ことでセルフホストできることを確認できる
Lisp慣れてないので、malでこれ書き直すのたぶん地獄だと思うので助かったmrsekut.icon
最初思ってたより20倍ぐらい大変だったが、得たものは大きい
Lispのこと、PureScriptのこと、処理系のこと、OSSのこと
やりづらかった点
ディレクトリの構成が良くないと思うmrsekut.icon
step1からstepAまではまだマシだが、その他のReaderとかTypesとかがstepを跨いで共通のものを使っている
だから、step1の時点では必要ない実装や型が、Typesなどに定義されている状態になっている
理想的には全てのファイルに対して、stepを区切るべきだと思う
でもそうすると、Readerの中にバグを見つけたら10箇所修正が必要なので微妙か..
標準関数がやたら多い
そういうものなのかも知れないがモチベを保つのが難しかった
テスト結果が見づらい
どれがfailしてどれがsuccessしたのか微妙にわかりにくいので、test caseを消しながら把握していった
もちろん「何行目で落ちましたよ」みたいのは出るが、それがある上で尚見づらい
各caseが独立していないのもやりづらかった
数10行上で定義した変数を使ったtestとかもあったので、↑に書いたようにtest case消しながらやっていくとたまにミスる
インクリメンタルな進め方でない
step1で、parserを作りきってしまうのはしんどかった
それ以降は「quote作ります」「macroを追加します」という感じなのでまだマシだった
以下は、各stepの概要と、作っていた時の気持ちを書いている
PureScript成分も各所に書いている
実装はコレ
Getting started
Makfileでテストする環境を整える
さらにはspagoのこともあまり知らなかったので躓いた
言語処理系作ったことあるし、すぐできるやろ、と舐めてたが最初から躓いた
Makefileの文法を調べ、spagoのoptionなどを調べ、ようやくテストが動くようになった
step 0
simpleなREPLを作る
入力をただ返すだけ
PureScriptだが、さっそくFFIをした
step 1
malの完全なParserを作る
Parsecは今まで何度か使ったことがあったので、Parsec固有の辛さみたいなのはさほどなかった
これを書いたおかげでやっと<$>とか*>のような、Functor, Applicative由来の記法や考え方が馴染んできた気がする
PureScript開発体験のココが良いmrsekut.icon
VSCodeの支援で、go to definitionで気軽にLibraryの中身が見れる
一つ一つのmoduleが小さくて、軽い気持ちで内部実装を読める
docsがごちゃごちゃしてない
malの解説では、正規表現を使って実装しているが、
HaskellやPureSciprtではparser combinatorで実装するので、解説はほぼ無意味だった
Haskell実装を大いに参考にした
Printerの"のescapeとかが地味に面倒だった
テストケースを通過することを目的にやった
そもそもLispをよく知らないのでtest case見て、こういうふうに書くのね、というのを知りながら進めた
step 2
Evalを作る
四則演算などをできるようにする
つまり標準関数が呼べるようになる
List, Vector, HashMapなどが評価できる
いや、評価自体はできないかmrsekut.icon
evalとevalAstを相互再帰して動かすことになるので、その構造を定義した感じ
Haskell実装は、解説と関数名がズレていた
evalAstをevalという名前で定義していた
これは2章の話でもないけど、Lispの場合全てが(fn arg1 arg2 ..)のような構造になる
だから、普通の(?)言語のASTのようにAdd Int Intのような定義をしない
極端に言えばListか、primitiveな値か、ぐらいの分類しか無い
ここはなるほどと思った
PureScriptの話としては、Exceptionなどを学んだ
Eval周辺の型がEffectなので、JSと同じノリでtry、throwができた
たぶん本当はあまりException使うべきではない気もするけどmrsekut.icon
このへんでpurtyに頼るのではなく、自分でformatしたほうがキレイだなということに気付いた
これ以降formatterを使っていない
step 3
Envを作る
let*やdef!も実装する
つまり、関数定義などができるようになる
code:purs(hs)
type Environment = Ref.Ref (List (Map String MalExpr))
この辺からHaskell実装とも乖離していく
と、思ったがstep 4,5あたりで詰まりまくったのでenvを受け渡す実装に戻した
PureScriptとしては型クラスやinstance、derivingなどを学んだ
初期の実装ではMalEnv型を作っていたので。
pursはhsよりも型クラスの区分がきめ細かいのでderiving instanceを8行ぐらい書いた
自前でExceptを実装しようと無理だったが、deriving instanceすれば難なくできたので感動した
モナド変換子の起動(runするところ)にめちゃくちゃ手間取った
実は最初はstep 1のReadlineをAffでやってたが、MalEnvの影響で無理になったのでEffectに変えた
これのせいでRepl上で左右カーソルキーでのカーソル移動ができなくなった
Elmの実装はこのへんからやたら大きくなってたので読むのをやめた
step 4
if,fn*,doと、いくつかの標準関数を実装する
標準関数どんなのがあるのかというのを実装しながら知った
PureScriptに割と慣れてきた
fn*はlambda式
&でoptionalな引数を取る
doは、すべての引数を評価して、最後の値を返却するもの
ここで実装する標準関数
list系の関数
list, list?, empty?, count
標準出力系の関数
prn, println, pr-str, str
似ているが地味に異なる
=, <, <=, >, >=, not
Core.pursはHaskell実装を参考にした
この時点で割と動くようになっっている
最初、MalEnvで実装してるときにfn*のtestを通すのにめちゃくちゃ苦労した
今も未解決だが。
これが無理どうしても無理なので、envを受け渡す実装に直した
その際にprint debug的なのをした
Effectを使っているのとShow instanceにしやすいPrinterを元から実装してたので案外すんなりdebugできた(その時の問題は解決してないけど)
step 5
ここが一番詰まったmrsekut.icon
これは継続の勉強にも繋がったので嬉しいmrsekut.icon
参考にしていたHaskellは遅延評価なので、何もしなくてもstep 5のテストに通る
そのためstep4とstep5に全く差がない
「Freeモナドを使えば回避できる」ということに行き着くまでにまず時間がかかった Trampoline不要で、Freeモナド使えば良いのかを知って、
Freeモナドを調べて理解し、
それを実装し、
とやったのでめちゃくちゃ時間がかかった
Freeを入れ込んだので、以下の5箇所を少し変更した
if
do
let
fn*
apply
step 6
ファイル読み込みなどを実装する
evalという関数を追加する
ASTを引数に取り、評価した結果を返す
以下の関数を追加した
read-string
mal levelのreadStr
code:prisp
(read-string "(+ 2 3)")
;=>(+ 2 3)
slurp
fileを読み込んで内容を文字列として返す
load-file
fileをloadする
PureScriptのimport構文みたいな感じmrsekut.icon
mal内で定義したり、Coreで定義したりする差はなんなんだろうというのは気になった
atom系の関数を追加した
atom
atom?
deref
reset!
swap!
ARGVをサポートする
コマンドライン引数を*ARGV*という名前で保存する
code:purs.hs
foreign import argv :: Array String
args :: List String
args = drop 2 $ fromFoldable argv
例えばこういうmal fileを用意しておいて
code:input.mal
(def! inc4 (fn* (a) (+ 4 a)))
(prn (inc4 (read-string (nth *ARGV* 0))))
こうやって実行する
code:shell
$ spago run --main Main --node-args "./input.mal 10"
14
コマンドライン引数の1つ目がファイル名、2つ目が*ARGV*にlistとして入る
引数は文字列のlistとして入る
code:input.mal
(prn *ARGV*)
code:shell
$ spago run --main Main --node-args "./input.mal 1 2 3 4 5"
("1" "2" "3" "4" "5")
step 7
quote, quasiquote, unquote, splice-unquoteを実装
また、その略記である', \`, ~, ~@を実装する
cons, concatを追加
vecも追加
この辺は言われたとおりに追加していくだけ
step 8
マクロを追加する
マクロ系の関数を追加する
is_macro, defmacro!, is_macro_call, macroexpand
macroは強力な割に実装自体は大したこと無い
list, vector系の関数を追加する
nth, first, rest
step 9
例外系の関数を追加する
try*/catch*を追加する
(try* abc (catch* exc (prn "exc is:" exc)))のような使い方をする
throw
諸々の便利標準関数を追加する
apply, map
nil?, true?, false?, symbol?
symbol
keyword, keyword?
vector, vector?
sequential?
hash-map
map?
assoc, dissoc
get, contains?, keys, vals
step A
セルフホストする
セルフホストのデバッグ、頭おかしくなるな
今回は幸いなことに読み込む方のmal.malにはバグがないことがかなり保証されている
更に標準関数を追加する
readline
time-ms
meta, with-meta
fn?
string?
number?
seq
conj
PR出した
step5をwipにした状態でいったん最後までやって出した
step5はすぐに終わるだろうと思ってたので出したがまじで全然終わらんかった
step5を保留したまま、step6~Aまで作ったので、
step5を修正すると、step6~A全部に修正が必要になってしまったので、PR出し直した
Dockerfileを用意するのが面倒すぎて、5ヶ月ほど放置してた
アドカレ投稿を機にDockerfileも出した
コードレビューで何回か往復した
レビュワーのkanakaさんが親切に対応してくださって助かった
最初time-msを雑に実装していたが、それのせいでパフォーマンステストに落ちていたので修正した
基本的にはInt型を使っているが、Unix timeがIntで収まらないので、そこだけNumberを使う必要がある
また、Lispは型が緩いので(?)、数値とtimeの演算ができるため、IntとNumberを組み合わせた数値演算ができる必要がある
この辺のテストは、PR出していないと見てなかったと思うので、良かった
今までもOSSに対して、小さなbug fixや、typo修正のPRを送ってたことはあるが、今回のような規模で出したのは初めてだった
英語でコミュニケーションむずいなとか、
めっちゃ親切にレビューしてくれるな〜、とか、
自分の対応が雑でちょっと反省だな、とか、
いろいろ思った